CPU speed is much faster than the speed of the main memory. CPU caches are used to bridge the speed gap so that the CPU is not slowed down as much when performing a memory access. CPU caches are small but are faster than the main memory. Recently used instructions and data are stored in the CPU cache. When the CPU references an address, it first checks whether the address is in the CPU cache. If so, it is called a cache hit, otherwise it is called a cache miss. The proportion of memory references which result in cache hits is called the cache hit rate. Cache hit rates are very important to the user's available computing power. Higher CPU cache hit rates result in higher processing efficiency.
Larger caches have higher hit rates, but CPU circuit technology limits the size of caches. Better cache replacement algorithms also have the potential to increase hit rates. Currently, the Least Recently Used (LRU) cache replacement method is used in CPU caches. LRU is believed to be able to exploit the temporal locality of programs which means that recently referenced addresses are more likely to be referenced again in the near future. Based on this theory, LRU tries to keep addresses which have just been referenced in the cache as long as possible. For programs with good locality, where the same addresses are referenced multiple times, replacement decisions made by LRU are acceptable. For programs with poor locality, such as network protocols and applications, where a significant portion of addresses are not reused, LRU's performance is less acceptable.
It is desired to address or ameliorate one or more of the shortcomings or disadvantages of prior cache management techniques, or to at least provide a useful alternative thereto.